package com.hot100.mid;

import java.util.Stack;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 两个倒叙链表之和
 * @date 2022/7/16 17:33
 */
public class Demo01 {


    /**
     * Definition for singly-linked list.
     * */
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    //int sum = num1 + num2;  c超位数了，不能通过全部用例，改成long仍然有3个用例通不过，所以只能采用方法2
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode node =new ListNode(0);
        ListNode pre=node;
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        //先将链表数据正过来，到栈中
        while (l1!=null){
            stack1.add(l1.val);
            l1=l1.next;
        }
        while (l2!=null){
            stack2.add(l2.val);
            l2=l2.next;
        }
        //出栈转成正常的十进制数字

        long num1=0,num2=0;
        while (!stack1.empty()){
            num1=num1*10;
            Integer pop = stack1.pop();
            num1=num1+pop;
        }
        while (!stack2.empty()){
            num2=num2*10;
            Integer pop = stack2.pop();
            num2=num2+pop;
        }
        //最终正序的数字为num1+num2
        long sum = num1 + num2;

        if (sum==0){
            return pre;
        }
        while (sum>0){
            node.next= new ListNode((int) (sum % 10));
            node=node.next;
            sum=sum/10;
        }


        return pre.next;
    }

    //这样两个数加起来，不会超过位数
    public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(-1), pre = dummyHead;
        int t = 0;
        while (l1 != null || l2 != null || t != 0) {
            if (l1 != null) {
                t += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                t += l2.val;
                l2 = l2.next;
            }
            pre.next = new ListNode(t % 10);
            pre = pre.next;
            t /= 10;
        }

        return dummyHead.next;
    }
}



